1. Field of the Invention
The present invention relates to an automatic trace determination apparatus for automatically determining optimal trace positions, from pads to corresponding vias on a substrate, by computation and a computer program for allowing a computer to perform this automatic trace determination process.
2. Description of the Related Art
In a semiconductor package such as a PBGA and an EBGA, electrode terminals of a semiconductor chip are electrically connected with pads (for example, wire bonding pads or flip-chip pads) and the pads are connected with vias (lands) and the vias are also connected with each other by traces (i.e., signal traces). Traces in the semiconductor package at least have to satisfy design rules in that clearances (of lines and spaces) between vias and traces and between traces themselves and so on can be secured and there is no unnecessary trace intersection (crossing). For example, a designer typically designs wiring routes of a semiconductor package by trial and error on a virtual plane using a CAD system.
FIG. 36 is a diagram illustrating nets to be wired in a semiconductor package. Hereinafter, when traces are shown in the accompanying figures, the shown traces are at least a portion of the traces on the substrate. Further, FIG. 37 is a diagram for describing legends of symbols for vias, pads and/or nets to be wired that are indicated in the figures attached to this specification. Hereinafter, the legends of FIG. 37 apply to figures showing the vias, pads and/or nets to be wired.
In a semiconductor package, traces are provided from pads connected with a semiconductor chip mounted in the center of a substrate toward vias provided in a peripheral region. In FIG. 36, as an example, nets to be wired from pads (bonding pads) arranged in a row to corresponding vias are indicated by straight lines (so-called “rats”). The traces in the semiconductor package have to secure clearances between the vias and the traces and between the traces themselves and eliminate unnecessary intersections between the traces. In the example shown in FIG. 36, there are intersections between the traces and, therefore, these intersections have to be resolved in the trace design.
As a wiring pattern design method that can automatically resolve the intersections described above, the present applicants invented a method in which only wiring routes are determined in advance in a rough wiring process and, then, in a trace formation process, traces are provided uniformly by checking clearances according to actual design rules and this invention is set forth in Japanese Unexamined Patent Publication No. 2002-083006. FIG. 38 is a diagram illustrating a trace design result in which the intersections between the nets shown in FIG. 36 are resolved by using a technique as set forth in Japanese Unexamined Patent Publication No. 2002-083006. In the figure, dotted lines indicate additional lines. This method sets the predetermined additional lines first and, then, determines the traces sequentially in the direction from the pads to the vias by using the additional lines.
Typically, in a semiconductor package, traces are provided from pads connected with a semiconductor chip mounted in the center of a substrate toward vias provided in a peripheral region and, therefore, the traces tend to be oriented in a substantially identical direction as shown in FIG. 38. In this specification, this direction of the traces is referred to as the “forward direction” and the traces oriented substantially in the forward direction are referred to as the “forward traces”. Such forward traces can be implemented relatively easily by computation using a computer.
If wirings in a semiconductor package at least satisfy design rules as described above, it can be said that a certain measure of success is achieved. In effect, however, it is often required that the wiring pattern not only satisfies the design rules but also that the wiring pattern is a “beautiful pattern” that are arranged regularly in a well-balanced manner to some extent. This is because the “beautiful pattern” may often result in reduction of manufacturing costs, electrical resistance and so on. Further, as a result of the well-balanced pattern, deformation of a substrate due to variation of temperature, humidity and so on may be restricted.
FIG. 39 is a diagram illustrating a case in which wiring routes of the nets shown in FIG. 36 are designed so that the traces are disposed in a well-balanced manner after resolving the intersections. As shown in FIG. 39, if the traces can bypass appropriately, a significantly better-balanced pattern can be implemented in comparison with the case of FIG. 38. As described above, the wiring in the semiconductor package is typically formed as a “forward wiring”. However, in actual cases, it is often advantageous that there are “routes that bypass vias (hereinafter simply referred to as the “bypass routes”)” so that a portion of the traces is oriented in the direction substantially opposite to the dominant direction from various viewpoints such as reduction of manufacturing costs and electrical resistance, restriction of deformation of the substrate and so on. Further, if such bypass routes are allowed, the possibility for the traces to reduce clearance errors may be increased and a margin in the pattern design may be created. In this specification, the wiring having the bypass routes that are oriented in the direction substantially opposite to the dominant direction is referred to as the “retrograde wiring”.
FIG. 40 is a diagram illustrating an example of a retrograde wiring. As shown in this figure, in the retrograde wiring, some traces may meander greatly and, therefore, it is difficult to automatize the wiring design by using a computer process. Therefore, at present, the designer designs the retrograde wiring manually depending on his experience and intuition. The designer designs optimal wiring routes that satisfy design rules and that do not include intersections between the wiring routes manually by making and modifying the wiring actually by trial and error while using a CAD/CAM system and viewing a display and, therefore, design quality and time required for design greatly depend on the designer's skill, experience, intuition and the like.
In the design of the retrograde wiring, a wiring method that reduces the burden on the designer and that implements the wiring design with stable quality is described in Tal Dayan, “A dissertation submitted in partial satisfaction of the requirements for the degree of doctor of philosophy in computer engineering”, June 1997, University of California Santa Cruz, USA. FIGS. 41A-41C are diagrams showing a principle of generation of a retrograde wiring according to a technique as set forth in a document entitled “Rubber-Band Based Topological Router”. Hereinafter, a character V combined with a numeral such as 1, 2 or so on is a reference symbol of vias, a character B combined with a numeral 1, 2 or so on is a reference symbol of pads, and a character W, W′, w″, W′″, w, w′ or w″ combined with a numeral 1, 2 or so on is a reference symbol of traces. Further, a character Q or Q′ combined with a numeral 1, 2 or so on is a reference symbol of intersections between the traces.
Here, as an example, it is assumed that a trace W1 connecting between a pad B1 and a via V1 intersects (crosses) with a trace W2 connecting between a pad B2 and a via V2 at an intersection Q1 as shown in FIG. 41A.
According to this technique, first, distances from the intersection Q1 formed between the two traces W1 and W2 to the vias V1 and V2, with which the two traces W1 and W2 are connected, respectively, are determined. In the example shown in FIG. 41A, the distance between the intersection Q1 and the via V2 is longer than the distance between the intersection Q1 and the via V1. As shown in FIG. 41B, the trace W2 associated with the longer distance is allowed to bypass the via V1, with which the trace W1 associated with the shorter distance is connected, so that the intersection Q1 can be resolved and the trace W2 is defined as a new trace W′2. As a result, retrograde wiring is generated as shown in FIG. 41C.
As described above, the trace associated with the shorter distance is not allowed to bypass the via with which the trace associated with the longer distance is connected but the trace associated with the longer distance is allowed to bypass the via with which the trace associated with the shorter distance is connected, because the increase in the total wiring length occurring as a result of this bypass can be more restricted in the latter case than in the former case.
In the technique as set forth in the document “Rubber-Band Based Topological Router”, the retrograde wiring can be designed according to design rules to some extent, but it is difficult to apply this technique to a complicated wiring as shown in FIG. 40. This is because the trace that is allowed to bypass may be very likely to intersect with other traces but the technique as set forth in the document “Rubber-Band Based Topological Router” still does not solve such problem. Thus, the automatization of the retrograde wiring design is still not achieved under present circumstances. After all, the designer has to design wiring routes of a semiconductor package on a virtual plane by trial and error depending on the designer's experience and intuition while actually manipulating a CAD system. In such manual pattern design by trial and error, as the required wiring pattern becomes more complicated, the effort, time and difficulty for achieving the optimal wiring pattern is increased. Further, unevenness in quality of finished products is also increased. In reality, because the manual pattern design by trial and error requires about one to three weeks' work and it is not economical to waste further time for pattern designing, the designer has to compromise with a certain design quality.
In view of the above problems, it is an object of the present invention to provide an automatic trace determination apparatus that can determine trace positions automatically by computation when optimal trace positions from pads to corresponding vias on a substrate are designed, even if a portion of the traces tends to be oriented in the direction substantially opposite to the dominant direction, and to provide a computer program for allowing a computer to perform this automatic trace determination process.